package demo;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 *   全排列
 */
class Solution23 {
	List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> usedList = new LinkedList<>();
	public List<List<Integer>> permute(int[] nums) {
		backtrace(nums, usedList);
		return result;
	}

	private void backtrace(int[] nums, LinkedList<Integer> usedList) {
		if (usedList.size() == nums.length) {
			result.add(new ArrayList<>(usedList));
		}
		for (int i = 0; i < nums.length; i++) {
			if (!usedList.contains(nums[i])) {
				usedList.add(nums[i]);
				backtrace(nums, usedList);
				usedList.removeLast();
			}
		}
	}

	public static void main(String[] args) {
		int[] arr = new int[]{1, 2, 3};
		Solution23 solution23 = new Solution23();
		solution23.permute(arr);
		System.out.println(solution23.result);

	}
}

